import java.util.Arrays;

public class Leetcode_1011 {

    /**
     *  方法：
     *      1. 每天运一件，可以运完（要求载重 min 为 货物的最大重量）
     *          min 不可以小于 货物最大载重，否则会出现 越下届现象
     *      2. 一天全部运完（要求载重 max 为 货物总重）
     *      3. 船的最小载重在这之间
     *      4. 利用 二分查找，寻找最小载重
     *      5. 附加条件：必须在 D 天内运完
     *          1. 当每次找到 mid中间位置 时，判定能否 D 天运完
     *              1. 若能，说明此载重，可以更小
     *                  极限思维：当载重足够大时，1 天就能运完，所以载重减小，天数增加，天数增加未到阈值，载重减小未到阈值
     *                      则选择，二分查找的 前半部分
     *              2. 若不能，说明此载重需要更大
     *                  极限思维：当载重为 min，需要最大天数（ 大于 D），所以，要使天数减少，载重要增加
     *                      则选择，二分查找的 后半部分
     *      6. 为了计算条件5，需要计算当前（mid）载重下，需要的天数
     */
    public int shipWithinDays(int[] weights, int D) {
        
        // 1. 寻找左右边界
        int left=0,right=0;
        for (int weight : weights) {
            if(left<=weight){
                left=weight;
            }
        }
//        // 另一种获取数组最大值的写法
//        left = Arrays.stream(weights).max().getAsInt();
        right= Arrays.stream(weights).sum();

        // 2. 折半查找
        while (left<right){
            // 确定中间位置（向下取整，3/2=1.5=1）
            int mid = (left+right)/2;

            // 3. 计算中间位置时，所需要的天数
            int needDay=0;  // 天数
            int cur=0;      // 当前累计重量
            for (int weight : weights) {
                cur += weight;
                if(cur>mid){
                    // 重置累计重量
                    cur = 0 + weight;
                    // 天数 +1
                    needDay++;
                }
            }
            // 因为最后一天肯定没超载，所以要补上这一天
            needDay++;

            // 4. 折半查找后续
            if(needDay>D){
                // 后半部分
                left = mid + 1;
            }
            else {
                // 前半部分
                right = mid;
            }
        }
        return left;
    }
}
